/*
实验15-4 有多少红黑树
分数 35
作者 曹鹏
单位 Google

给定正整数 n，存在多少棵有 n 个内部结点（即空结点不算）的不同的红黑树？
输入格式：

输入在一行中给出一个正整数 n（≤500）。
输出格式：

在一行中输出有 n 个内部结点的不同的红黑树的个数。因为这个数字可能非常大，所以只要输出答案对 1000000007 取余的结果。
输入样例：

5

输出样例：

8
*/

/*
方法思路

红黑树的结构可以映射到2-3-4树的结构，其中每个节点可以有1、2或3个键。每个2-3-4树的节点对应红黑树中的一个结构，
其构造方式数目取决于键的数量。通过动态规划，我们可以计算满足条件的2-3-4树的数目，并考虑每个节点的构造方式数目。

    动态规划状态定义：dp[k]表示键数目总和为k的2-3-4树的数量，乘以对应的构造方式数目。

    状态转移：对于每个可能的根节点键数m（1、2、3），计算其子树的组合数目，并累加到当前状态。

    卷积优化：通过维护生成函数的二次、三次和四次幂的系数数组，高效计算子树的组合数目。
*/

#include <iostream>

using namespace std;

const int MOD = 1000000007;

int main() {
    int n;
    cin >> n;

    long long dp[501] = {0};
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = (dp[i] + dp[j - 1] * dp[i - j]) % MOD;
        }
    }
    cout << dp[n] << endl;

    return 0;
}